package algorithm.difficult;

import java.util.Stack;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.difficult
 * @Author: 江岸
 * @CreateTime: 2021-04-03 12:01
 * @Description: 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * <p>
 * 示例 2：
 * <p>
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Trap42 {
    public static void main(String[] args) {
        fun1(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }

    //按照列求 每列往左边或者右边找到最高的墙，如果两边都比自己高，则用矮的那个减去自己的高度，就是这一列能装的水
    //可以提前遍历动态规划 保存左/右 最高的数字数组
    public static int fun1(int[] height) {
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int n = height[i];
            int left = i - 1;
            int leftMax = 0;
            while (left >= 0) {
                leftMax = Math.max(leftMax, height[left]);
                left--;
            }
            int right = i + 1;
            int rightMax = 0;
            while (right < height.length) {
                rightMax = Math.max(rightMax, height[right]);
                right++;
            }
            if (leftMax > n && rightMax > n) {
                //res = res + leftMax<rightMax?leftMax:rightMax - n;
                res = res + (leftMax < rightMax ? leftMax : rightMax) - n;
            }
        }
        return res;
    }

    //双指针

    /**
     * 所以这里要用到两个指针，left 和 right，从两个方向去遍历。
     * <p>
     * 那么什么时候从左到右，什么时候从右到左呢？根据下边的代码的更新规则，我们可以知道
     * <p>
     * max_left = Math.max(max_left, height[i - 1]);
     * <p>
     * height [ left - 1] 是可能成为 max_left 的变量， 同理，height [ right + 1 ] 是可能成为 right_max 的变量。
     * <p>
     * 只要保证 height [ left - 1 ] < height [ right + 1 ] ，那么 max_left 就一定小于 max_right。
     * <p>
     * 因为 max_left 是由 height [ left - 1] 更新过来的，而 height [ left - 1 ] 是小于 height [ right + 1] 的，而 height [ right + 1 ] 会更新 max_right，所以间接的得出 max_left 一定小于 max_right。
     * <p>
     * 反之，我们就从右到左更。
     * <p>
     * 作者：windliang
     * 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int fun2(int[] height) {
        int sum = 0;
        int max_left = 0;
        int max_right = 0;
        int left = 1;
        int right = height.length - 2; // 加右指针进去
        for (int i = 1; i < height.length - 1; i++) {
            //从左到右更
            if (height[left - 1] < height[right + 1]) {
                max_left = Math.max(max_left, height[left - 1]);
                int min = max_left;
                if (min > height[left]) {
                    sum = sum + (min - height[left]);
                }
                left++;
                //从右到左更
            } else {
                max_right = Math.max(max_right, height[right + 1]);
                int min = max_right;
                if (min > height[right]) {
                    sum = sum + (min - height[right]);
                }
                right--;
            }
        }
        return sum;
    }

    //单调栈
    public int fun4(int[] height) {
        int res = 0;
        //从左到右遍历，栈底元素大
        Stack<Integer> stack = new Stack<>();
        //（左最高 - 第二高） * 下标差
        for (int i = 0; i < height.length; i++) {
            //栈中元素小于右边，可以计算
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int mid = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                //计算
                Integer peek = stack.peek();
                res += (Math.min(height[peek], height[i]) - height[mid]) * (i - peek - 1);
            }
            stack.push(i);
        }
        return res;
    }


    /**
     * 说到栈，我们肯定会想到括号匹配了。我们仔细观察蓝色的部分，可以和括号匹配类比下。每次匹配出一对括号（找到对应的一堵墙），就计算这两堵墙中的水。
     * <p>
     * 我们用栈保存每堵墙。
     * <p>
     * 当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。
     * <p>
     * 如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。
     * <p>
     * 总体的原则就是，
     * <p>
     * 当前高度小于等于栈顶高度，入栈，指针后移。
     * <p>
     * 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
     * <p>
     * 作者：windliang
     * 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int fun3(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        int current = 0;
        while (current < height.length) {
            //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
            while (!stack.empty() && height[current] > height[stack.peek()]) {
                int h = height[stack.peek()]; //取出要出栈的元素
                stack.pop(); //出栈
                if (stack.empty()) { // 栈空就出去
                    break;
                }
                int distance = current - stack.peek() - 1; //两堵墙之前的距离。
                int min = Math.min(height[stack.peek()], height[current]);
                sum = sum + distance * (min - h);
            }
            stack.push(current); //当前指向的墙入栈
            current++; //指针后移
        }
        return sum;
    }

}
